package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//广度优先搜索:4ms 92%,5.6MB 7%
func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}
	queue := []*TreeNode{root}
	for i := 0; i < len(queue); i++ {
		if maxDiff(maxDepth(queue[i].Left), maxDepth(queue[i].Right)) > 1 {
			return false
		}
		if queue[i].Left != nil {
			queue = append(queue, queue[i].Left)
		}
		if queue[i].Right != nil {
			queue = append(queue, queue[i].Right)
		}
	}
	return true
}

//深度优先搜索:8ms 51%,5.5MB 90% , go可能对这个做了优化，多条件同时运行，遇到错误直接返回，所以和下面的自下而上时间相似
func isBalanced1(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return maxDiff(maxDepth(root.Left), maxDepth(root.Right)) < 2 && isBalanced(root.Left) && isBalanced(root.Right)
}

//深度优先搜索(自下而上,遇到false及时返回):8ms 51%,5.5MB 90%
func isBalanced2(root *TreeNode) bool {
	return height(root) != -1
}
func height(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftHeight := height(root.Left)
	rightHeight := height(root.Right)
	if leftHeight == -1 || rightHeight == -1 || maxDiff(leftHeight, rightHeight) > 1 {
		return -1
	}
	return max(leftHeight, rightHeight) + 1
}

//dfs递归深度
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return max(maxDepth(root.Left)+1, maxDepth(root.Right)+1)
}

func max(i, j int) int {
	if i > j {
		return i
	} else {
		return j
	}
}

func maxDiff(i, j int) int {
	if i > j {
		return i - j
	} else {
		return j - i
	}
}

func main() {
	fmt.Println(isBalanced(&TreeNode{5, nil, nil}))
	fmt.Println(isBalanced1(&TreeNode{5, nil, nil}))
	fmt.Println(isBalanced2(&TreeNode{5, nil, nil}))
}
